package leetcode.秋招.字节跳动.字节研发在线编程;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/25 15:29
 * @description：https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=190&&tqId=35221&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking
 */
public class NC45实现二叉树先序中序和后序遍历 {
    @Test
    public void test() {
        Solution solution = new Solution();
        solution.threeOrders(new TreeNode(1, new TreeNode(2, null, null), new TreeNode(3, null, null)));
    }

    public class TreeNode {
      int val = 0;
      TreeNode left = null;
      TreeNode right = null;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public class Solution {
        /**
         *
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
        public int[][] threeOrders (TreeNode root) {
            // write code here
            List<Integer> preList = preOrder(root);
            List<Integer> infixList = infixOrder(root);
            List<Integer> postList = postOrder(root);
            int[][] res = new int[3][infixList.size()];
            for (int i = 0; i < res[0].length; i++) {
                res[0][i] = preList.get(i);
            }
            for (int i = 0; i < res[0].length; i++) {
                res[1][i] = infixList.get(i);
            }
            for (int i = 0; i < res[0].length; i++) {
                res[2][i] = postList.get(i);
            }
            return res;
        }

        public List<Integer> infixOrder(TreeNode node) {
            if (node == null) return null;
            ArrayList<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode tmp = node;
            while (tmp != null || !stack.isEmpty()) {
                if (tmp != null) {
                    stack.push(tmp);
                    tmp = tmp.left;
                } else {
                    tmp = stack.pop();
                    list.add(tmp.val);
                    tmp = tmp.right;
                }
            }
            return list;
        }

        public List<Integer> postOrder(TreeNode node) {
            ArrayList<Integer> list = new ArrayList<>();
            if (node == null) return list;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode tmp = node;
            TreeNode pre = null;
            while (tmp != null || !stack.isEmpty()) {
                while (tmp != null) {
                    stack.push(tmp);
                    tmp = tmp.left;
                }
                if (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.right == null || tmp.right == pre) {
                        tmp = stack.pop();
                        list.add(tmp.val);
                        pre = tmp;
                        tmp = null;
                    } else {
                        tmp = tmp.right;
                    }
                }
            }
            return list;
        }

        public List<Integer> preOrder(TreeNode node) {
            ArrayList<Integer> list = new ArrayList<>();
            if (node == null) return list;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(node);
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                list.add(cur.val);
                if (cur.right != null)
                    stack.push(cur.right);
                if (cur.left != null)
                    stack.push(cur.left);
            }
            return list;
        }
    }
}
